#ifndef __DYNAMICPPROGRAMMING_H__
#define __DYNAMICPPROGRAMMING_H__

#include "filter.h"

#include <limits.h>
#include <float.h>
#include <assert.h>


class min_compare           //lets use a class to make code more generic:
{							//chose a class to compare wether searching MAX or MIN path
		public:   
		bool min_compare::cmp(const float &val1, const float &val2) {return val1<val2;}  //should make no difference if < or <=
};

class max_compare    
{
        public:   
		bool max_compare::cmp(const float &val1, const float &val2) {return val1>val2;} 
};


template <class T>
void DynamicPath(pip::Image<T> &in,int n=3, bool max=false)
{

	assert(n%2);   //n is not odd 
	
	float init(0);
	if(!max)
	{
		min_compare compare;                 //class for comparision -looking for min or max?
		init = numeric_limits<float>::max();
		dynpro(in,n,init, compare);       // call function before 'compare-class' is out of scope...
	}
	else
	{
		max_compare compare; 
		init = numeric_limits<float>::min();
		dynpro(in,n,init, compare);
	}
}

	//in order to use compare-classes...
    // I had to use another function (since I wasn't able to use pointer to different classes 
	// OR the instances of the classes went out of scope after their 'if-loop')

template <class T,class  U>
void dynpro(pip::Image<T> &in,int n, float init, U compare)
{
	T Mi(0), Ma(0);
	getMinMaxImage(in, Mi, Ma);
	float compensate(0);
	if(Mi<0)
		compensate=-1*float(Mi);  // it was required, that the function is templated... otherwise i would have converted all images to float before passing them to dynamic-path...
							   // 'compensate' will help to 

	//create an image to save the costs for each node ... float, since costs can be high...
	pip::Image<float> costs(Dimension(in.dim(0),in.dim(1)),n/2,border_constant,init);
	//in order to avoid "IF OUTSIDE IMAGE" control loops let us border the image!
	// !!! the chosen value is always the most undesired (min or max) value possible, so the pixel outside will not be chosen...
	costs.fill(init);	

	float best(0);     // best remembers current min or max

	for (int f=0; f < in.dim(0);++f)  
		costs(f,0)=float(in(f,0))+compensate;     // the first line has costs identical to pixelvalues in the input-image

	for(int line = 1;  line < in.dim(1); ++line) // do not process first line ...
	{
		for(int row=0; row  < in.dim(0); ++row)
		{
			best=init;							//search for min or max costs to reach THIS node
			for(int next=-n/2; next <= n/2; ++next){
				if(compare.cmp(costs(next+row,line-1),best))
				{
					best=costs(next+row,line-1);  //there are N options, remember the best one
				}
			}
			costs(row,line)= best + float(in(row,line))+ compensate;              //increase the cost according to its best result
		}
	}
	pip::exportFile(costs,"cost-image_float.pip"); 
	//cost calculation ready

	//start backtrace

	
	float all_costs(0),white_value(0);
	int global(0),candidate(0),pixel_num(0);               
	best=init;                 
	for(int x=0; x < in.dim(0); ++x)            //the global minimum should be found in the last line, now
	{
		white_value +=float(in(x,costs.dim(1)-1));
		if(compare.cmp(costs(x,costs.dim(1)-1),best))
		{
			best=costs(x,costs.dim(1)-1);  
			global=x;							//remember coordinates of global min/max in last line
		}
	}
	std::cout << " 'Absolute' cost of path: " << costs(global,costs.dim(1)-1)<< endl;
	std::cout << " Cost of path: " << costs(global,costs.dim(1)-1)-(compensate*in.dim(1));
	all_costs+=float(in(global,costs.dim(1)-1));

	if((white_value/in.dim(0))>((Ma-Mi)/2))    //the color should be inside the range of occuring colors...
		in(global,in.dim(1)-1)=Mi;
	else 
		in(global,in.dim(1)-1)=Ma;

	white_value=0;
	


	for(int line = (in.dim(1)-2);  line >= 0  ; --line) 
	{
		best = init;
		for(int next=0; next <= n/2; ++next){  //there are N options, where we could have come from
			for(int correction=-1; correction <= 1; correction+=2)
			{
				if(compare.cmp(costs(correction*next+global,line),best))
				{
					best=costs(correction*next+global,line);  
					candidate=global+next*correction;		  // remember the lowest position
				}
			}
		}
		all_costs+=float(in(candidate,line));
		global = candidate;
	

//CODE BEFORE exercise 8
		// let us average over the nighbour-hood pixel to determine the color of the optimal path...
		//pixel_num=0;
		//white_value=0;
		//for(int x=-1; x <= 1;++x){
		//	for(int y=-1; y <= 1;++y){
		//		if(global+x < in.dim(0) && line+y < in.dim(1) && global+x > 0 && line+y > 0)
		//		{
		//			white_value+=float(in(global+x,line+y));
		//			pixel_num++;
		//		}
		//	}
		//}
		//
		////if(true)
		//if((white_value/pixel_num)>((Ma-Mi)/2))    //the color should be inside the range of occuring colors...
		//	in(global,line)=Mi;
		//else 
		//	in(global,line)=Ma;

//exercise 8
		//different coloring
		for(int x=-4; x <= 4;++x){
			for(int y=-1; y <= 1;++y){
				if(global+x < in.dim(0) && line+y < in.dim(1) && global+x > 0 && line+y > 0)
				{
					if(x==0)   // to better identify the middle
						in(global+x,line+y)=(Ma-Mi)/5;
					else
						in(global+x,line+y)=255;
				}
			}
		}


	}
	std::cout << " [control cost from backtrace: " << all_costs <<  "] \n ";
	
}

// to display images on webpage, i can't use pip images... CONVERT EVERYTHING TO BMP...
template <class T>
pip::Image<unsigned char> convertAllToUnsignedChar(const pip::Image<T> &input)
{
  pip::Image<unsigned char> output;
  T min, max;
  getMinMaxImage(input, min, max);

  output.resize(input.dimension());

  if (min == max) {
    output.fill(128);
    return output;
  }
  
  float scale( float(numeric_limits<unsigned char>::max()) / (max - min));
  std::cout << int(max - min) << "   \n";
  std::cout << int(T(numeric_limits<unsigned char>::max())) << "   \n";
   std::cout << scale << "   \n";
  for (int z = 0; z < input.dim(2); ++z) {
    for (int y = 0; y < input.dim(1); ++y) {
      for (int x = 0; x < input.dim(0); ++x) {
		  //std::cout << int(unsigned char((scale * (input(x, y, z) - min))))<< "   ";
        output(x, y, z) = (unsigned char)(scale * (input(x, y, z) - min));
      }
    }
  }
  return output;
}


#endif